Discrete optimal transport solvers do not scale well on dense large problemssince they do not explicitly exploit the geometric structure of the costfunction. In analogy to continuous optimal transport we provide a framework toverify global optimality of a discrete transport plan locally. This allowsconstruction of an algorithm to solve large dense problems by considering asequence of sparse problems instead. The algorithm lends itself to beingcombined with a hierarchical multi-scale scheme. Any existing discrete solvercan be used as internal black-box.Several cost functions, including the noisysquared Euclidean distance, are explicitly detailed. We observe a significantreduction of run-time and memory requirements.
展开▼
